1. Technical Field
The present invention relates to a method and system for error correcting codes in general, and in particular to a method and system for decoding convolutional codes. Still more particularly, the present invention relates to a method and system for decoding tailbiting convolutional codes.
2. Description of the Prior Art
Information signals communicated between a transmitter and a receiver via a communication channel can be corrupted by various noises associated with the channel. Thus, a technique known as error correction coding is typically employed to mitigate the effects of channel noises within a communication channel. By introducing redundancy in the information signals to be communicated, channel coding can reduce the likelihood of channel noise corrupting the information signals. In most cases, the technique of channel coding has been proven to be quite successful, even for long distance communications such as between a base station on Earth to a spacecraft approaching a distant planet.
Convolutional codes are a class of error correcting codes that are well-known in the art for mitigating the effects of channel noise. One example of such convolutional codes, which has been adopted as a standard for North American digital cellular radio communications, is known as IS-130 by the International Telecommunication Union. IS-130 employs a type of convolutional code that is also known in the art as a tailbiting convolutional code, in which a frame or block of information is encoded and communicated in a blockwise manner. The term tailbiting refers to the fact that the convolutional encoder begins and ends in the same encoding state. Although the decoder is aware that the encoder begins and ends in the same encoding state, the decoder is unaware of the value of that state. In other words, the initial encoding state of the encoder is unknown to the decoder; and in fact, for arbitrary data, the encoder may have started in any of the possible states with approximately the same probability. Hence, the fundamental difficulty encountered in designing a decoder for tailbiting convolutional codes is that the decoder must be capable of determining the initial encoding state of the encoder in a very short time.
In the prior art, a maximum-likelihood decoder, better known as a Viterbi decoder, may be utilized for decoding tailbiting convolutional codes. A Viterbi decoder decodes an actual corrupted sequence of received signals by finding the most likely sequence of uncorrupted signals. Similar to other types of decoders, a Viterbi decoder is also unaware of an encoder's starting state, hence the Viterbi decoder must perform Viterbi decoding exhaustively for all possible starting states. Although the outcome is always correct, this method is unacceptably slow for many applications. For example, if the number of the storage elements in the encoder is K, the time to decode is always 2.sup.K longer than that of the encoder's non-tailbiting counterpart. As a result, a Viterbi decoder places great demands on computational resources. Needless to say, it would be desirable to provide an improved technique for decoding tailbiting convolutional codes, which yields good levels of error protection with less computational burden.